package com.sourcetrip.algorithm.sort.insertion;

import com.sourcetrip.algorithm.abs.AbstractCustomedObjectSort;

/**
 * @author: ZhouBert
 * @date: 2020/12/30
 * @description: 十大排序算法之四：插入排序（的对象比较版本）的优化版本 --
 * 优化方向：
 * 根据【从有序数组中找到对应插入位置】这个命题，用二分搜索进行优化！
 * BUT
 * 即使进行了二分查找的优化，但是由于依然需要挪动 O(n) + n 个元素的挪动，所以依然是 O(n)
 * 的时间复杂度！跟 heap sort 差距很大！
 */
public class InsertionCustomedSortV2ByBinarySearch<E> extends AbstractCustomedObjectSort<E> {

	/**
	 * 写法：
	 * 依然使用 Insertion Sort 的框架
	 * 由于本次不是比较一个就进行一次挪动，而是先完全找到了，再进行挪动！
	 * 所以可以看做是 V1 版本 Double For Loop 的改进版本！
	 *
	 * @param objectArr
	 */
	@Override
	protected void sortArr(E[] objectArr) {
		int size = objectArr.length;
		int swapIndex = 0;
		E temp = null;
		for (int i = 1; i < size; i++) {
			temp = objectArr[i];
			//1.通过二分查找找到插入的位置（第一个大于元素值的索引）
			swapIndex = binarySearch(objectArr, 0, i, temp);

			//2.执行批量挪动
			for (int j = i; j > swapIndex; j--) {
				objectArr[j] = objectArr[j - 1];
			}
			objectArr[swapIndex] = temp;
		}

	}


	//region	core methods

	/**
	 * TODO:二分搜索的设计关键：[begin, end)
	 * 这样设计的好处：
	 * size = begin - end
	 * 每次不符合时，begin=mid+1 or end=mid-1;
	 *
	 * @param objectArr
	 * @param begin
	 * @param end
	 * @param item      比较的元素
	 * @return 返回 第一个大于 item 的索引位置(即交换的位置)
	 */
	private int binarySearch(E[] objectArr, int begin, int end, E item) {
		int mid = (begin + end) >> 1;
		while (begin < end) {
			if (compare(objectArr[mid], item) <= 0) {
				begin = mid + 1;
			} else {
				//因为查找区域在 [begin, end) 内，所以 end=mid
				end = mid;
			}
			mid = (begin + end) >> 1;
		}
		//此时 begin==end && begin==swapIndex
		return begin;
	}

	//endregion

}
